// LinkedLists.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <iostream>
#include <memory>

using namespace std;

template <class T>
class Node
{
public:
    explicit Node(T value) : _value(value)
    {
    }

    Node(T value, shared_ptr<Node> next) : _value(value), _next(next)
    {
    }

    ~Node()
    {
        //cout << "Node with value " << _value << " is deleted." << endl;
    }

    T value() const
    {
        return _value;
    }

    shared_ptr<Node> next() const
    {
        return _next;
    }

    void setNext(shared_ptr<Node> next)
    {
        _next = next;
    }

private:
    T _value;
    shared_ptr<Node<int>> _next;
};

typedef shared_ptr<Node<int>> NodePtr;

void print(NodePtr root)
{
    while (root)
    {
        cout << root->value() << ", ";
        root = root->next();
    }
    cout << endl;
}

void deleteDuplicates(NodePtr root)
{
    auto current = root;
    while (current != nullptr)
    {
        auto next = current->next();
        auto prvious = current;

        while (next)
        {
            if (next->value() == current->value())
            {
                prvious->setNext(next->next());
                next.reset();
                next = prvious->next();
            }
            else
            {
                prvious = next;
                next = next->next();
            }
        }

        current = current->next();
    }
}

void testDeleteDuplicates()
{
    NodePtr root =    make_shared<Node<int>>(0, 
                                    make_shared<Node<int>>(1, 
                                    make_shared<Node<int>>(2,
                                    make_shared<Node<int>>(3,
                                    make_shared<Node<int>>(1,
                                    make_shared<Node<int>>(5,
                                    make_shared<Node<int>>(2, nullptr)))))));

    deleteDuplicates(root);

    auto current(root);
    while (current)
    {
        cout << current->value() << ", ";
        current = current->next();
    }
    cout << endl;
}

NodePtr nthToLast(NodePtr root, int n)
{
    auto front = root;
    auto back = root;

    for (int i = 0; i < n; i++)
    {
        if (!front)
        {
            return nullptr;
        }
        front = front->next();
    }

    while (front)
    {
        back = back->next();
        front = front->next();
    }

    return back;
}

void testNthToLast()
{
    NodePtr root =    make_shared<Node<int>>(0, 
                                    make_shared<Node<int>>(1, 
                                    make_shared<Node<int>>(2,
                                    make_shared<Node<int>>(3,
                                    make_shared<Node<int>>(1,
                                    make_shared<Node<int>>(5,
                                    make_shared<Node<int>>(2, nullptr)))))));

    auto ret = nthToLast(root, 2);
    if (ret)
    {
        cout << ret->value() << endl;
    }
}

bool deleteNode(NodePtr& node)
{
    auto next = node->next();
    if (next)
    {
        swap(*node, *next);
        next->setNext(nullptr);
        return true;
    }
    else
    {
        return false;
    }
}

void testDeleteNode()
{
    NodePtr middle = make_shared<Node<int>>(1,
                                    make_shared<Node<int>>(5,
                                    make_shared<Node<int>>(2, nullptr)));

    NodePtr root =    make_shared<Node<int>>(0, 
                                    make_shared<Node<int>>(1, 
                                    make_shared<Node<int>>(2,
                                    make_shared<Node<int>>(3,
                                    middle))));
    deleteNode(middle); 
    print(root);
}

NodePtr partition(NodePtr root, int threshold)
{
    if (!root || !root->next())
    {
        return root;
    }

    auto previous = root;
    auto current = previous->next();
    while (current)
    {
        if (current->value() < threshold)
        {
            previous->setNext(current->next());
            current->setNext(root);
            root = current;
        }
        else
        {
            previous = current;
        }
        current = previous->next();
    }
    return root;
}

void testPartition()
{
    NodePtr root =  make_shared<Node<int>>(0, 
                    make_shared<Node<int>>(1, 
                    make_shared<Node<int>>(2,
                    make_shared<Node<int>>(3,
                    make_shared<Node<int>>(4,
                    make_shared<Node<int>>(5,
                    make_shared<Node<int>>(6, nullptr)))))));

    auto ret = partition(root, 3);
    print(ret);
}

NodePtr intToList(int x)
{
    NodePtr root = make_shared<Node<int>>(x % 10, nullptr);
    auto current = root;
    x /= 10;
    while (x != 0)
    {
        current->setNext(make_shared<Node<int>>(x % 10, nullptr));
        current = current->next();
        x /= 10;
    }

    return root;
}

int listToInt(NodePtr x)
{
    int ret = 0;
    auto current = x;
    while (current != nullptr)
    {
        ret = ret * 10 + current->value();
        current = current->next();
    }

    return ret;
}

NodePtr addList(NodePtr x, NodePtr y)
{
    auto sum = listToInt(x) + listToInt(y);
    return intToList(sum);
}

void testAddList()
{
    auto x = intToList(234);
    auto y = intToList(789);

    auto ret = addList(x, y);
    print(ret);
}

bool isCircularList(NodePtr root)
{
    auto fast = root;
    auto slow = root;
    
    while(fast)
    {
        slow = slow->next();
        
        if (!fast->next())
        {
            break;
        }

        fast = fast->next()->next();

        if (fast == slow)
        {
            return true;
        }
    }

    return false;
}

void testIsCircularList()
{
    NodePtr last = make_shared<Node<int>>(2, nullptr);
    NodePtr middle = make_shared<Node<int>>(1,
                    make_shared<Node<int>>(5,
                    last));
    last->setNext(middle);

    NodePtr root = make_shared<Node<int>>(0, 
                    make_shared<Node<int>>(1, 
                    make_shared<Node<int>>(2,
                    make_shared<Node<int>>(3,
                    middle))));

    if (isCircularList(middle))
    {
        cout << "The given list is circular." << endl;
    }
}

pair<NodePtr, bool> isParlinDrome_(NodePtr root, int length)
{
    if (length == 0)
    {
        return make_pair<NodePtr, bool>(nullptr, true);
    }
    else if (length == 1)
    {
        return make_pair<NodePtr, bool>(root->next(), true);
    }
    else if (length == 2)
    {
        return make_pair<NodePtr, bool>(root->next()->next(), root->value() == root->next()->value());
    }

    auto result = isParlinDrome_(root->next(), length - 2);

    return make_pair<NodePtr, bool>(result.first->next(), result.second ? root->value() == result.first->value() : false); 
}

bool isParlinDrome(NodePtr root, int length)
{
    auto ret = isParlinDrome_(root, length);
    return ret.second;
}

void testIsParlinDrome()
{
    NodePtr root =  make_shared<Node<int>>(0, 
                    make_shared<Node<int>>(1, 
                    make_shared<Node<int>>(2,
                    make_shared<Node<int>>(3,
                    make_shared<Node<int>>(2,
                    make_shared<Node<int>>(1,
                    make_shared<Node<int>>(0, nullptr)))))));

    if (isParlinDrome(root, 7))
    {
        cout << "The given list is parlindrome." << endl;
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    testDeleteDuplicates();
    testNthToLast();
    testDeleteNode();
    testPartition();
    testAddList();
    testIsCircularList();
    testIsParlinDrome();

    cin.get();
    return 0;
}

